package leetcode4;
import java.util.*;

public class Day12 {

    //1049-最后一块石头的重量
    public int lastStoneWeightII(int[] stones) {
        //问题先转换成“目标和”问题，也就是里面的元素相加或者相减
        //然后想办法得出smu/2，也就是一半为sum/2时，两者之差最小
        //最终转化：在数组中选择一些数，尽可能的等于sum/2，也就是背包的容量为sum/2,尽可能的装满
        int sum = 0, n = stones.length;
        for(int i = 0;i < n;i++) sum += stones[i];
        int aim = sum/2;
        int[][] dp = new int[n+1][aim+1];//从前i个元素中，选取一些数，让和尽可能=j
        for(int i=1;i<n+1;i++) {
            for(int j=1;j<aim+1;j++) {
                dp[i][j] = dp[i-1][j];//不选i
                if(j>=stones[i-1]) {//选i
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }
        //
        return Math.abs((sum-dp[n][aim])-dp[n][aim]);
    }




    //494.目标和
    public int findTargetSumWays(int[] nums, int target) {
        //选择每个数字为负数或者正数
        //问题转化成从n个数中选择几个数字，和为a时有多少种解法
        int n = nums.length;
        int sum = 0;
        for(int i=0;i<n;i++) {
            sum += nums[i];
        }
        int a = (sum + target)/2;
        if(a<0 || (sum + target)%2!=0) return 0;
        //从前i个物体中选择，组成和为j一共有多少种选法
        int[] dp = new int[a+1];
        dp[0]=1;
        for(int i=1;i<n+1;i++) {
            for(int j=a;j>=nums[i-1];j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }
        return dp[a];
    }


    //分割等和子串 -- 一维数组优化版
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i=0;i<n;i++) {
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        sum /= 2;
        //dp[i][j]:从前i个物体中选择，是否能构成和为sum/2的值
        boolean[] dp = new boolean[sum+1];
        //初始化第一列
        // for(int i=0;i<n+1;i++) dp[i][0]=true;
        dp[0]=true;
        for(int i=1;i<n+1;i++) {
            for(int j=sum;j>=nums[i-1];j--) {
                //不选i位置 || 选i位置，是否可以凑到j-nums[i-1]
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[sum];
    }



    //0-1背包 -- 一维数组优化方案
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[] dp = new int[V+1];
        for(int i=1;i<n+1;i++)
            for(int j=V;j>=vw[i-1][0];j--) {
                dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
            }
        return dp[V];
    }


    //牛客网 -- NC309 完全背包
    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        // write code here
        int[][] dp = new int[n+1][v+1]; //从前i个物体中选，总体积不超过j的最大价值
        //dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]] + w[i]) 最后一个位置是否选择，或者选择多个
        //dp[i][j-v[i]]+w[i]是通过计算替换得出的一个统一表达式
        //如果体积恰好装满，则-1表示凑不到的情况
        int[][] arr = new int[n+1][2];
        for(int i=1;i<n+1;i++) {
            for(int j=0;j<2;j++) {
                arr[i][j] = nums.get(i-1).get(j);
            }
        }
        for(int i=1;i<n+1;i++) {
            for(int j=1;j<v+1;j++) {
                int t = 0;
                if(j-arr[i][0] >= 0) {
                    t = dp[i][j-arr[i][0]] + arr[i][1];
                }
                dp[i][j] = Math.max(dp[i-1][j],t);
            }
        }
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(dp[n][v]);
        //处理问题（2）
        int[][] fullDp = new int[n+1][v+1]; //如果不能装满则是-1
        fullDp[0][0]=0;
        for(int i=1;i<v+1;i++) fullDp[0][i]=-1;
        for(int i=1;i<n+1;i++) {
            for(int j=1;j<v+1;j++) {
                fullDp[i][j] = fullDp[i-1][j];
                //判断是否可以装下i物体，并且恰好装满
                if(j >= arr[i][0] && fullDp[i][j-arr[i][0]]!=-1) {
                    fullDp[i][j] = Math.max(fullDp[i][j],fullDp[i][j-arr[i][0]] + arr[i][1]);
                }
            }
        }
        if(fullDp[n][v] == -1) ret.add(0);
        else ret.add(fullDp[n][v]);
        return ret;
    }
}
